package com.mlh.binarytree;

import java.util.HashMap;
import java.util.Map;

/**
 * @author 缪林辉
 * @date 2024/8/26 15:32
 * @DESCRIPTION
 */
//给定两个整数数组 preorder 和 inorder ，
// 其中 preorder 是二叉树的先序遍历， inorder 是同一棵树的中序遍历，请构造二叉树并返回其根节点。
public class 从前序与中序遍历序列构造二叉树 {
    //对于任意一颗树而言，前序遍历的形式总是
    // [ 根节点, [左子树的前序遍历结果], [右子树的前序遍历结果] ]
    // 即根节点总是前序遍历中的第一个节点。
    // 而中序遍历的形式总是
    // [ [左子树的中序遍历结果], 根节点, [右子树的中序遍历结果] ]
    Map<Integer,Integer>map;
    //利用递归
    public TreeNode method1(int[] preorder, int[] inorder) {
        //方便查找前序遍历根节点在后续遍历中的位置，利用哈希表来记录中序遍历的值和下标的对应
        map=new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i],i);
        }
        return recursion(preorder,inorder,0,preorder.length-1,0,preorder.length-1);
    }

    public TreeNode recursion(int[] preorder, int[] inorder,int preHead,int preTail,int inHead,int inTail){
        if(preHead>preTail){
            return null;
        }
        //利用中序遍历 来计算前序遍历中左右子树的节点个数，进而进入下一次递归
        int rootVal=preorder[preHead];
        TreeNode node = new TreeNode(rootVal);
        int rootIndex = map.get(rootVal);
        int leftLen=rootIndex-inHead;//计算左子树的节点个数 不需要额外算右子树的节点个数了
        node.left=recursion(preorder,inorder,preHead+1,preHead+leftLen,inHead,rootIndex-1);
        node.right=recursion(preorder,inorder,preHead+leftLen+1,preTail,rootIndex+1,inTail);
        return node;
    }


    public TreeNode practice(int[] preorder, int[] inorder) {
        Map<Integer,Integer>map=new HashMap<>();
        for (int i = 0; i < inorder.length; i++) {
            map.put(inorder[i],i);
        }
        return practiceRecursion(preorder,inorder,0, preorder.length-1,0,inorder.length-1,map);
    }
    //左子树的前序遍历和中序遍历结果，以及右子树的前序遍历和中序遍历结果，我们就可以递归地对构造出左子树和右子树，再将这两颗子树接到根节点的左右位置。
    //构造子树的前序数组和后序数组 ，不断递归即可
    public TreeNode practiceRecursion(int[] preorder, int[] inorder,int preLeft,int preRight,int inLeft,int inRight,Map<Integer,Integer>map){
        if(preLeft>preRight){
            return null;
        }
        TreeNode root=new TreeNode(preorder[preLeft]);
        int index = map.get(preorder[preLeft]);
        int leftLen=index-inLeft;
        root.left= practiceRecursion(preorder,inorder,preLeft+1,preLeft+leftLen,inLeft,index-1,map);
        root.right=practiceRecursion(preorder,inorder,preLeft+leftLen+1,preRight,index+1,inRight,map);
        return root;
    }
}
